package com.cat.gridChart;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/rotting-oranges/description/
 * @create 2025/9/7 20:30
 * @since JDK17
 */

public class Solution15 {
    static int[][] q = new int[110][2];
    static int[][] d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int orangesRotting(int[][] grid) {
        int n = grid.length, m = grid[0].length, ans = 0, t = 0, h = 0, tot = 0;
        boolean[][] vis = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {  // 烂橘子
                    q[t++] = new int[]{i, j};
                    vis[i][j] = true;
                } else {
                    tot += grid[i][j];
                }
            }
        }
        while (h < t && tot > 0) {
            ans++;
            for (int end = t; h < end; h++) {
                var p = q[h];   // 弹出一个
                for (int i = 0; i < 4; i++) {
                    int nx = p[0] + d[i][0], ny = p[1] + d[i][1];
                    if (nx == -1 || nx == n || ny == -1 || ny == m || vis[nx][ny] || grid[nx][ny] != 1) {
                        continue;
                    }
                    tot--;
                    vis[nx][ny] = true;
                    q[t++] = new int[]{nx, ny};
                }
            }
        }

        return tot == 0 ? ans : -1;
    }
}
